1. Field of the Invention
The present invention relates generally to a channel interleaving/deinterleaving apparatus and a control method thereof, and in particular, to a channel interleaving/deinterleaving apparatus in a communication system using low density parity check codes and a control method thereof.
2. Description of the Related Art
With the rapid development of mobile communication systems, there is a need to develop technology capable of transmitting a large volume of data, approaching the capacity of wire networks, in wireless networks. Due to increasing demand for high-speed, high-capacity communication systems capable of processing and transmitting a variety of information, such as image and wireless data, as well as the voice data, increasing system transmission efficiency using an appropriate channel coding scheme is an essential factor for improvement of the system performance.
However, mobile communication systems, due to their characteristics, may inevitably suffer from an error caused by noise, interference and/or fading according to channel conditions during data transmission. Therefore, mobile communication systems can suffer a loss of information data due to error.
In order to reduce information data loss, mobile communication systems normally use various error control schemes according to channel characteristics, thereby contributing to improvements of system reliability. Of the error control schemes, an error correction code-based error control scheme is most popularly used.
Typical error correction codes include turbo codes and Low Density Parity Check (LDPC) codes.
It is well known that the turbo code is superior in performance gain to a convolutional code conventionally used for error correction, during high-speed data transmission. The turbo code is advantageous in that it can efficiently correct an error caused by noises generated in a transmission channel, thereby increasing reliability of the data transmission. The LDPC code can be decoded using an iterative decoding algorithm based on a sum-product algorithm in a factor graph. Because a decoder for the LDPC code uses a sum-product algorithm-based iterative decoding algorithm, it is lower in complexity than a decoder for the turbo code. In addition, the decoder for the LDPC code is easy to implement with a parallel processing decoder, compared with the decoder for the turbo code.
Shannon's channel coding theorem shows that reliable communication is possible only at a data rate not exceeding a channel capacity. However, Shannon's channel coding theorem has proposed no detailed channel coding/decoding method for supporting a data rate up to the channel capacity limit. Although a random code having a very large block size shows performance approximating the channel capacity limit of Shannon's channel coding theorem, it is actually impossible to implement a Maximum A Posteriori (MAP) or Maximum Likelihood (ML) decoding method because of its heavy calculation load.
The turbo code was proposed by Berrou, Glavieux and Thitimajshima in 1993, and has superior performance approximating the channel capacity limit of Shannon's channel coding theorem. The proposal of the turbo code triggered an active research on iterative decoding and graphical expression of codes, and LDPC codes proposed by Gallager in 1962 are newly spotlighted in the research. Cycles exist in a factor graph of the turbo code and the LDPC code, and it is well known that iterative decoding in the factor graph of the LDPC code where cycles exist is not ideal. Also, it has been experimentally proven that the LDPC code has excellent performance through iterative decoding. The LDPC code known to have the highest performance shows performance having a difference of only about 0.04 decibels at the channel capacity limit of Shannon's channel coding theorem at a bit error rate (BER) 10−5, using a block size 107. In addition, although an LDPC code defined in Galois field (GF) with q>2, i.e. GF(q), increases in complexity in its decoding process, it is much superior in performance to a binary code. However, there has been provided no satisfactory theoretical description of successful decoding by an iterative decoding algorithm for the LDPC code defined in GF(q).
The LDPC code, proposed by Gallager, is defined by a parity check matrix in which major elements have a value of 0 (Null) and minor elements except for the elements having the value of 0 have a non-zero value, for example, i.e. a value of 1. For convenience, it will be assumed herein that the non-zero value is a value of 1. For example, an (N, j, k) LDPC code is a linear block code having a block length N, and is defined by a sparse parity check matrix in which each column has j elements having a value of 1, each row has k elements having a value of 1, and all of the elements except for the elements having the value of 1 have a value of 0.
An LDPC code in which a weight of each column in the parity check matrix is fixed to ‘j’ and a weight of each row in the parity check matrix is fixed to ‘k’ as stated above, is called a “regular LDPC code.” Herein, the “weight” refers to the number of elements having a non-zero value among the elements constituting the generating matrix and parity check matrix. On the contrary, an LDPC code in which the weight of each column in the parity check matrix and the weight of each row in the parity check matrix are not fixed is called an “irregular LDPC code.”
It is generally known that the irregular LDPC code is superior in performance to the regular LDPC code. However, in the case of the irregular LDPC code, because the weight of each column and the weight of each row in the parity check matrix are not fixed, i.e. are irregular, the weight of each column in the parity check matrix and the weight of each row in the parity check matrix must be properly adjusted in order to guarantee the excellent performance.
With reference to FIG. 1, a description will now be made of a parity check matrix of an (8, 2, 4) LDPC code as an example of the (N, j, k) LDPC code.
FIG. 1 is a diagram illustrating a parity check matrix of a general (8, 2, 4) LDPC code.
Referring to FIG. 1, a parity check matrix H of the (8, 2, 4) LDPC code is comprised of 8 columns and 4 rows, wherein a weight of each column is fixed to 2 and a weight of each row is fixed to 4. Because the weight of each column and the weight of each row in the parity check matrix are regular, the (8, 2, 4) LDPC code illustrated in FIG. 1 is a regular LDPC code.
The parity check matrix of the (8, 2, 4) LDPC code has been described so far with reference to FIG. 1. Next, a factor graph of the (8, 2, 4) LDPC code described in connection with FIG. 1 will be described hereinbelow with reference to FIG. 2.
FIG. 2 is a diagram illustrating a factor graph of the (8, 2, 4) LDPC code of FIG. 1.
Referring to FIG. 2, a factor graph of the (8, 2, 4) LDPC code is comprised of 8 variable nodes of x1 202, x2 204, x3 206, x4 208, x5 210, x6 212, x7 214 and x8 216, and 4 check nodes 218, 220, 222 and 224. When an element having a value of 1, i.e. a non-zero value, exists at the point where an ith row and a jth column of the parity check matrix of the (8, 2, 4) LDPC code cross each other, a branch is created between a variable node xi and a jth check node.
Because the parity check matrix of the LDPC code has a very small weight as described above, it is possible to perform decoding through iterative decoding even in a block code having a relatively long size, that exhibits performance approximating a channel capacity limit of Shannon's channel coding theorem, such as a turbo code, while continuously increasing a block size of the block code. MacKay and Neal have proven that an iterative decoding process of an LDPC code using a flow transfer scheme approximates an iterative decoding process of a turbo code in performance.
In order to generate a high-performance LDPC code, the following conditions should be satisfied.
(1) Cycles in a Factor Graph of an LDPC Code Should Be Considered.
The term “cycle” refers to a loop formed by the edges connecting the variable nodes to the check nodes in a factor graph of an LDPC code, and a length of the cycle is defined as the number of edges constituting the loop. A long cycle means that the number of edges connecting the variable nodes to the check nodes constituting the loop in the factor graph of the LDPC code is large. In contrast, a short cycle means that the number of edges connecting the variable nodes to the check nodes constituting the loop in the factor graph of the LDPC code is small.
As cycles in the factor graph of the LDPC code become longer, the performance efficiency of the LDPC code increases, for the following reasons. When long cycles are generated in the factor graph of the LDPC code, it is possible to prevent performance degradation such as an error floor occurring when too many cycles with a short length exist in the factor graph of the LDPC code.
(2) Efficient Coding of an LDPC Code Should Be Considered.
It is difficult for the LDPC code to undergo real-time coding compared with a convolutional code or a turbo code because of its high coding complexity. In order to reduce the coding complexity of the LDPC code, a Repeat Accumulate (RA) code has been proposed. However, the RA code also has a limitation in reducing the coding complexity of the LDPC code. Therefore, efficient coding of the LDPC code should be taken into consideration.
(3) Degree Distribution in a Factor Graph of an LDPC Code Should Be Considered.
Generally, an irregular LDPC code is superior in performance to a regular LDPC code, because a factor graph of the irregular LDPC code has various degrees. The term “degree” refers to the number of edges connected to the variable nodes and the check nodes in the factor graph of the LDPC code. Further, the phrase “degree distribution” in a factor graph of an LDPC code refers to a ratio of the number of nodes having a particular degree to the total number of nodes. It has been proven by Richardson that an LDPC code having a particular degree distribution is superior in performance.
However, a detailed scheme of performing channel interleaving/deinterleaving taking characteristics of the LDPC code into account in the communication system using the LDPC code has never been considered. Accordingly, there is a need for a detailed scheme of performing channel interleaving/deinterleaving taking characteristics of the LDPC code into account in the communication system using the LDPC code.
Generally, the LDPC code is expressed using a parity check matrix. Up to date, the research on the LDPC code has been based on Binary Phase Shift Keying (BPSK) and Quadrature Phase Shift Keying (QPSK) modulations. However, in the next generation mobile communication system requiring a high data rate, there is a need for research on the LDPC code suitable for high-order modulation such as 16-ary Quadrature Amplitude Modulation (16QAM) and 64QAM in order to use the LDPC code.